{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CRC 校验码\n",
    "\n",
    "- https://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art008"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 多项式计算\n",
    "\n",
    "$$\n",
    "{\n",
    "    12x^5 + 23x^4 + 57x^3 + 79x^2 + 69x + 60\n",
    "    \\over \n",
    "    4x^3 + 5x^2 +  9x + 12\n",
    "}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([5.0, 2.0, 3.0], [0.0, 0.0, 0.0])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# numerator 分子, denominator 分母\n",
    "def divide_poly(num: list, den: list):\n",
    "    qcount = len(num) - len(den) + 1\n",
    "    quotient = [0 for _ in range(qcount)]\n",
    "\n",
    "    for idx in range(qcount):\n",
    "        nidx = len(num) - 1 - idx\n",
    "        qidx = qcount - 1 - idx\n",
    "\n",
    "        quotient[qidx] = num[nidx] // den[-1]\n",
    "\n",
    "        for d in range(len(den)):\n",
    "            num[qidx + d] -= den[d] * quotient[qidx]\n",
    "\n",
    "    return quotient, num[: len(den) - 1]\n",
    "\n",
    "\n",
    "num = [60.0, 69.0, 79.0, 57.0, 23.0, 12.0]\n",
    "den = [12.0, 9.0, 5.0, 4.0]\n",
    "divide_poly(num, den)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二进制多项式除法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0.0, 1.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 1.0], [0.0, 1.0, 1.0, 1.0])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def divide_binary(num: list, den: list):\n",
    "    qcount = len(num) - len(den) + 1\n",
    "    quotient = [0 for _ in range(qcount)]\n",
    "\n",
    "    for idx in range(qcount):\n",
    "        nidx = len(num) - 1 - idx\n",
    "        qidx = qcount - 1 - idx\n",
    "\n",
    "        quotient[qidx] = (num[nidx] // den[-1]) % 2\n",
    "\n",
    "        for d in range(len(den)):\n",
    "            num[qidx + d] -= den[d] * quotient[qidx]\n",
    "            num[qidx + d] = (num[qidx + d]) % 2\n",
    "\n",
    "    return quotient, num[: len(den) - 1]\n",
    "\n",
    "# 1101_0110_1100_00\n",
    "num = [\n",
    "    0.0, 0.0,\n",
    "    0.0, 0.0, 1.0, 1.0,\n",
    "    0.0, 1.0, 1.0, 0.0,\n",
    "    1.0, 0.0, 1.0, 1.0,\n",
    "]\n",
    "\n",
    "den = [1.0, 1.0, 0.0, 0.0, 1.0]\n",
    "\n",
    "divide_binary(num, den)\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 计算 CRC32"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0xa3830348\n",
      "0xd202ef8d\n"
     ]
    }
   ],
   "source": [
    "import binascii\n",
    "\n",
    "crc = binascii.crc32(b\"ABC\")\n",
    "print(f\"{crc:#x}\")\n",
    "\n",
    "crc = binascii.crc32(b\"\\x00\")\n",
    "print(f\"{crc:#x}\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 反转比特序列\n",
    "\n",
    "实际上的字节序在物理上存储就是比特完全反转，但是一些关于字节序的描述给出了如下的例子：\n",
    "\n",
    "- 大端：`0x12345678`\n",
    "- 小段：`0x78563412`\n",
    "\n",
    "这是由于，机器对小端字节序的解释，造成了这个现象；"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "01000001 10000010\n",
      "41 82\n"
     ]
    }
   ],
   "source": [
    "def reverse_bits(value, width=8):\n",
    "    string = b = \"{:0{width}b}\".format(value, width=width)\n",
    "    return int(string[::-1], 2)\n",
    "\n",
    "\n",
    "a = ord(\"A\")\n",
    "print(f\"{a:08b} {reverse_bits(a):08b}\")\n",
    "print(f\"{a:x} {reverse_bits(a):x}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 1. 0. 0. 0. 0. 1. 1.]\n",
      " [0. 1. 0. 0. 0. 0. 1. 0.]\n",
      " [0. 1. 0. 0. 0. 0. 0. 1.]]\n",
      "[0 1 0 1] 5\n",
      "[1 0 1 0] A\n",
      "[0 1 0 1] 5\n",
      "[1 0 1 1] B\n",
      "[0 1 0 0] 4\n",
      "[0 0 1 1] 3\n",
      "[0 0 1 1] 3\n",
      "[1 0 1 0] A\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "den = [int(bit) for bit in f'{0x104C11DB7:b}']\n",
    "den.reverse()\n",
    "\n",
    "num = []\n",
    "for ch in b\"ABC\\x00\\x00\\x00\\x00\": # 补足 CRC32 字节\n",
    "    num.insert(0, [float(bit) for bit in f'{ch:08b}'])\n",
    "\n",
    "num = np.array(num)\n",
    "print(num.reshape(-1, 8))\n",
    "\n",
    "quotient, remainder = divide_binary(num.reshape(-1), den)\n",
    "crc = np.array(remainder)[::-1].reshape(-1, 4)\n",
    "\n",
    "for c in crc:\n",
    "    c = c.astype(np.int_)\n",
    "    print(c, f\"{c[3] + (c[2] << 1) + (c[1] << 2)  + (c[0] << 3):X}\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 单个整型"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0x5a5b433a\n",
      "0x0\n"
     ]
    }
   ],
   "source": [
    "def compute_crc0(data, len, divisor):\n",
    "    while len > 0:\n",
    "        len -= 1\n",
    "        if data & 0x8000_0000:\n",
    "            data = ((data << 1) ^ divisor) & 0xFFFF_FFFF\n",
    "        else:\n",
    "            data = (data << 1) & 0xFFFF_FFFF\n",
    "    return data\n",
    "\n",
    "\n",
    "divisor = 0x04C11DB7\n",
    "# data = 0x8242C200\n",
    "data = reverse_bits(0x434241, 32)\n",
    "# print(f'{data:x}')\n",
    "crc = compute_crc0(data, 3 * 8, divisor)\n",
    "print(f\"{crc:#x}\")\n",
    "\n",
    "crc = compute_crc0(0, 8, divisor)\n",
    "print(f\"{crc:#x}\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 多字节"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0x5a5b433a\n",
      "0x0\n"
     ]
    }
   ],
   "source": [
    "def compute_crc1(data, len, divisor):\n",
    "    crc = 0\n",
    "\n",
    "    for i in range(len):\n",
    "        crc = (crc ^ (reverse_bits(data[i]) << 24)) & 0xFFFF_FFFF\n",
    "\n",
    "        for k in range(8):\n",
    "            if crc & 0x8000_0000:\n",
    "                crc = ((crc << 1) ^ divisor) & 0xFFFF_FFFF\n",
    "            else:\n",
    "                crc = (crc << 1) & 0xFFFF_FFFF\n",
    "\n",
    "    return crc\n",
    "\n",
    "divisor = 0x04C11DB7\n",
    "data = b\"ABC\"\n",
    "\n",
    "crc = compute_crc1(data, 3, divisor)\n",
    "print(f\"{crc:#x}\")\n",
    "\n",
    "crc = compute_crc0(0, 8, divisor)\n",
    "print(f\"{crc:#x}\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "你可能会有疑问，在一开始我们只处理了一个字节，但是后面以或操作却是整个 32 位校验和；这是由于异或的一些美好的性质：它具有交换律和结合律。\n",
    "\n",
    "| a   | b   | c   |\n",
    "| --- | --- | --- |\n",
    "| 0   | 0   | 0   |\n",
    "| 0   | 1   | 1   |\n",
    "| 1   | 0   | 1   |\n",
    "| 1   | 1   | 0   |"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ISO 的改进\n",
    "\n",
    "上个实现直到输入的第一个 1 位才生效。这可能看起来不像一个重要的问题，但这意味着一个输入加上一串前导 0 不会被 CRC 计算检测为错误。\n",
    "\n",
    "出于这个原因，官方的 CRC32 标准建议从全 1 开始，而不是 全 0；最后做取反操作；\n",
    "\n",
    "- https://www.iso.org/standard/8559.html\n",
    "- https://cdn.standards.iteh.ai/samples/8559/69473f113177492d9711be845cb6f992/ISO-3309-1991.pdf\n",
    "- https://cdn.standards.iteh.ai/samples/8561/ee3e6fc1cc8641fabff5257e9660cf07/ISO-IEC-3309-1993.pdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0xa3830348\n",
      "0xd202ef8d\n"
     ]
    }
   ],
   "source": [
    "def compute_crc2(data, len, divisor):\n",
    "    crc = 0xFFFF_FFFF\n",
    "\n",
    "    for i in range(len):\n",
    "        crc = (crc ^ (reverse_bits(data[i]) << 24)) & 0xFFFF_FFFF\n",
    "\n",
    "        for k in range(8):\n",
    "            if crc & 0x8000_0000:\n",
    "                crc = ((crc << 1) ^ divisor) & 0xFFFF_FFFF\n",
    "            else:\n",
    "                crc = (crc << 1) & 0xFFFF_FFFF\n",
    "\n",
    "    return reverse_bits((~crc) & 0xFFFF_FFFF, 32)\n",
    "\n",
    "\n",
    "divisor = 0x04C11DB7\n",
    "data = b\"ABC\"\n",
    "crc = compute_crc2(data, 3, divisor)\n",
    "print(f\"{crc:#x}\")\n",
    "crc = compute_crc2(b\"\\x00\", 1, divisor)\n",
    "print(f\"{crc:#x}\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 小端字节序的优化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0xa3830348\n"
     ]
    }
   ],
   "source": [
    "def compute_crc3(data, len, divisor):\n",
    "    crc = 0xFFFFFFFF\n",
    "\n",
    "    for i in range(len):\n",
    "        crc = (crc ^ data[i]) & 0xFFFFFFFF\n",
    "        for k in range(8):\n",
    "            if crc & 1:\n",
    "                crc = ((crc >> 1) ^ divisor) & 0xFFFFFFFF\n",
    "            else:\n",
    "                crc = (crc >> 1) & 0xFFFFFFFF\n",
    "    return crc ^ 0xFFFFFFFF\n",
    "\n",
    "\n",
    "# divisor = 0xEDB88320\n",
    "divisor = reverse_bits(0x04C11DB7, 32)\n",
    "data = b\"ABC\"\n",
    "crc = compute_crc3(data, 3, divisor)\n",
    "print(f\"{crc:#x}\")\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 生成表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0xa3830348\n"
     ]
    }
   ],
   "source": [
    "def crc_byte(byte, divisor):\n",
    "    for k in range(8):\n",
    "        if byte & 1:\n",
    "            byte = ((byte >> 1) ^ divisor) & 0xFFFF_FFFF\n",
    "        else:\n",
    "            byte = (byte >> 1) & 0xFFFF_FFFF\n",
    "    return byte\n",
    "\n",
    "\n",
    "def compute_crc4(data, len, divisor):\n",
    "    crc = 0xFFFFFFFF\n",
    "\n",
    "    for i in range(len):\n",
    "        crc = (crc_byte((crc ^ data[i]) & 0xFF, divisor) ^ (crc >> 8)) & 0xFFFF_FFFF\n",
    "\n",
    "    return crc ^ 0xFFFFFFFF\n",
    "\n",
    "\n",
    "divisor = 0xEDB88320\n",
    "data = b\"ABC\"\n",
    "crc = compute_crc4(data, 3, divisor)\n",
    "print(f\"{crc:#x}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0xa3830348\n"
     ]
    }
   ],
   "source": [
    "def crc_byte(byte, divisor=0xEDB88320):\n",
    "    for k in range(8):\n",
    "        if byte & 1:\n",
    "            byte = ((byte >> 1) ^ divisor) & 0xFFFF_FFFF\n",
    "        else:\n",
    "            byte = (byte >> 1) & 0xFFFF_FFFF\n",
    "    return byte\n",
    "\n",
    "\n",
    "crc_table = [crc_byte(i) for i in range(256)]\n",
    "\n",
    "\n",
    "def compute_crc5(data, len):\n",
    "    crc = 0xFFFFFFFF\n",
    "\n",
    "    for i in range(len):\n",
    "        crc = (crc_table[(crc ^ data[i]) & 0xFF] ^ (crc >> 8)) & 0xFFFF_FFFF\n",
    "\n",
    "    return crc ^ 0xFFFFFFFF\n",
    "\n",
    "\n",
    "data = b\"ABC\"\n",
    "crc = compute_crc5(data, 3)\n",
    "print(f\"{crc:#x}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "test",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.16"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
